package com.krahets88.stack;

import org.junit.jupiter.api.Test;

import java.util.Stack;

/**
 * 题目：https://leetcode.cn/problems/decode-string/
 * 算法思路:
 * 利用栈存储: 使用栈来存储解码过程中的字符和数字。遇到左括号'[' 之前的字符和数字都会被压入栈中。
 * 遇到右括号解码: 遇到右括号']'时，开始出栈并进行解码操作：
 * 从栈中不断弹出字符，直到遇到左括号'['，并将弹出的字符拼接成一个字符串。
 * 弹出左括号'['.
 * 弹出栈顶的数字，代表重复次数。
 * 将拼接的字符串重复指定的次数，并将结果压入栈中。
 * 最终结果: 遍历完整个编码字符串后，栈中存储的就是解码后的字符串。
 * 步骤详解:
 * 初始化: 创建一个字符串栈 item_stack 用于存储解码过程中的字符和数字，创建一个 StringBuilder 对象 tempStr 用于拼接数字字符。
 * 遍历字符串: 遍历编码字符串 s 中的每个字符 item。
 * 处理数字:
 * 如果 item 是数字，将其追加到 tempStr 中，用于拼接成完整的数字字符串。
 * 如果 item 不是数字，并且 tempStr 中有内容，说明之前已经拼接了数字，则将 tempStr 转换为字符串并压入 item_stack，然后清空 tempStr。
 * 处理字符: 如果 item 不是 ']'， 则将 item 转换为字符串并压入 item_stack。
 * 处理右括号: 如果 item 是 ']'：
 * 创建一个空字符串 str_char 用于存储解码后的字符串片段。
 * 循环弹出栈顶元素，直到遇到 '[':
 * 如果弹出的元素不是 '['，则将其拼接到 str_char 的头部 (实现字符串反转)。
 * 如果弹出的元素是 '['，则退出循环。
 * 将栈顶元素（代表重复次数的数字）弹出并转换为整数 num。
 * 将 str_char 重复 num 次，并将结果压入栈中。
 * 生成最终结果: 遍历完字符串后，将栈中所有元素依次弹出并拼接到结果字符串 res_str 中，最终返回 res_str。
 * 重要点解析:
 * 如何将数字暂存到字符串中并统一入栈:
 * 代码中使用 StringBuilder tempStr 存储连续的数字字符。
 * 遇到非数字字符时，检查 tempStr 是否为空，如果不为空，说明之前有数字字符，将其转换为字符串并入栈。
 * 出栈顺序与入栈顺序相反，如何还原成原来顺序的字符串:
 * 代码中通过在 while 循环内部 将每次从栈中弹出的字符添加到 str_char 的 头部，实现了字符串的反转。
 * 例如，如果栈中依次弹出 "k", "j", "e"，则 str_char 会被构建为 "e" -> "je" -> "kje"，从而实现了字符串的反转。
 */
public class Question394 {
    @Test
    public void test1() {
        Solution solution = new Solution();
        System.out.print(solution.decodeString("100[le]"));
    }
}

class Solution {
    public String decodeString(String s) {
        Stack<String> item_stack = new Stack<>();
        char[] char_str = s.toCharArray();
        StringBuilder tempIntStr = new StringBuilder();
        for (char item : char_str) {    //不为 ]就一直入栈
            if (item != ']') { // 入栈
//                入栈的时候将数字的字符串组合在一起入栈
                if (Character.isDigit(item)){
                    tempIntStr.append(item);
                }else {
                    if(tempIntStr.length() > 0){
                        item_stack.push(tempIntStr.toString());
                        tempIntStr = new StringBuilder();
                    }
                    item_stack.push(String.valueOf(item));
                }
            } else {     // 为]就出栈
                String tempStr = "";
                while (true) {
                    String index_item = String.valueOf(item_stack.pop());
                    if (!index_item.equals("[")) {
                        // index需要先反转，再加入到tempStr
//                        tempStr += index_item;
                        tempStr = index_item + tempStr;
                    } else {
                        break;
                    }
                }
                int num = Integer.valueOf(item_stack.pop());
                // 错误点，当jk e j三个元素连续反转的时候jk变成了kj
//                item_stack.push(new StringBuilder(tempStr).reverse().toString().repeat(num));\
                item_stack.push(new StringBuilder(tempStr).toString().repeat(num));
            }
        }
        String res_str = "";
        while (!item_stack.isEmpty()) {
            res_str = item_stack.pop() + res_str;
        }
        return res_str;
    }
}